package LeetCode._02算法基础.day16动态规划;

/**
 * @author 挚爱之夕
 * @version 中等
 * @implSpec 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 * 注意 这个数列必须是 严格 递增的。
 * 输入: [1,3,5,4,7]
 * 输出: 2
 * 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
 * @since 2022 - 09 - 12 - 11:02
 */
public class _673最长递增子序列的个数 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 4, 7};
        System.out.println(findNumberOfLIS(nums));
    }
    public static int findNumberOfLIS(int[] nums) {
        int res = 0;
        int len = nums.length;
        //dp[i] 以 i 位结尾的最长子序列的长度
        int[] dp = new int[len];
        //count[i] 以 i 位结尾的最长子序列个数
        int[] count = new int[len];
        for(int i = 0; i < len; i++){
            dp[i] = 1;
            count[i] = 1;
        }

        int maxLen = 1;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){  //构成更长的序列
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }else if(dp[j] + 1 == dp[i]){   //找到一样长的序列
                        count[i] += count[j];
                    }
                }
            }
            if(dp[i] > maxLen){ //更新最长递增长度，更新最长递增序列个数
                maxLen = dp[i];
                res = count[i];
            }else if(dp[i] == maxLen){  //找到与maxLen相同长度的最长递增子序列
                res += count[i];
            }
        }
        return res;
    }
}
